package com.leetcode.algorithm.y22.m06;

/**
 * 1575. 统计所有可行路径
 * 
 * https://leetcode.cn/problems/count-all-possible-routes/
 * 
 * 2 <= locations.length <= 100
 * 1 <= locations[i] <= 109
 * 所有 locations 中的整数 互不相同 。
 * 0 <= start, finish < locations.length
 * 1 <= fuel <= 200
 * 
 * @author jie.deng
 *
 */
class Question1575Solution01 {

	public int countRoutes(int[] locations, int start, int finish, int fuel) {
		int len = locations.length;

		// DP状态定义
		// dp[i][j]表示从 i 到 finish (初始拥有的汽油总量j)所有可能路径的数目
		int[][] dp = new int[len][fuel + 1];
		dp[finish][0] = 1;
		for (int j = 1; j <= fuel; j++) {
			for (int i = 0; i < len; i++) {
				if (Math.abs(locations[i] - locations[finish]) <= j) {
					int routesCount = i == finish ? 1 : 0;
					for (int i2 = 0; i2 < len; i2++) {
						if (i != i2) {
							// i ---> i2(i2!=start && i2!=finish) ---> finish
							int fuelRemain = j - Math.abs(locations[i] - locations[i2]);
							if (fuelRemain >= 0) {
								routesCount += dp[i2][fuelRemain];
								routesCount %= 1000000007;
							}
						}
					}
					dp[i][j] = routesCount;
				}
			}
		}

		return dp[start][fuel];
	}

}